An array is a common data structure used to store data in a computer or other data processing system. The array data structure typically arranges a plurality of array elements in a list, with each array element accessed via a unique index. For example, many computer memory systems are organized into arrays, with individual memory locations or groups of memory locations functioning as array elements, and with each element having a unique memory address functioning as an index thereto.
A primary benefit of the array data structure is its random access nature, which permits individual elements to be accessed quickly, e.g., by maintaining pointers or indices to the elements. However, one drawback to the array data structure is that modifications to the array which change the overall size of the array elements are difficult to handle in an efficient manner. In particular, it is desirable for any data structure to be compact and utilize no more memory space than necessary. Thus, when an array element is modified, e.g., by deleting the element, adding the element to the array, or, for arrays which support variable size elements, changing the size of the element, each element which follows the modified element must often be updated, or moved, from its previous location in memory. Moving elements, however, may require a time consuming memory transfer operation, thereby degrading the performance of the memory system.
In the alternative, each array element may be "padded" with unused memory locations, thereby enabling elements to "grow" or "shrink" without affecting the starting addresses of the subsequent elements in the array. However, this technique can be extremely wasteful because unused memory is interspersed within the array. Moreover, this technique still is not able to accommodate array element deletions and additions, nor larger array element modifications that overrun the available padding.
One particular application in which arrays are utilized is in memory compression, where high storage density and fast memory transfer operations are desired. In some memory compression applications, pages of data are arranged into arrays of blocks which are then compressed into frames to minimize the amount of memory that must be recompressed in response to a modification of compressed data. Whenever data in a frame is modified, the frame typically must be recompressed, which often modifies the size of the frame and/or the amount of information stored in the frame. Each frame in the page that follows the recompressed frame must often then be updated, e.g., moved and/or recompressed, to optimize compression of the page. When data stored in a frame near the beginning of a page is modified, often most or all of the frames in the page must be updated, which may have a significant impact on the overall performance of the memory system.
Therefore, a substantial need exists for a manner of minimizing performance degradations associated with modifying elements in an array, particularly in the areas of memory compression and the like.